1. Field of the Invention
The present invention relates to a backup system, method, and program for backing up data in preparation for a disaster or accident by distributing and allocating the data to a plurality of local storages, and, particularly relates to a backup system, method, and program for increasing tolerance against failure by redundantly encoding data which is to be distributed to local storages.
2. Description of the Related Arts
Conventionally, in order to protect data in a storage such as a magnetic disk device from failure, unexpected accidents, etc., RAID (Redundant Arrays of Independent Disks) is provided as a generally used technique. Although the levels of RAID include RAID 0 to RAID 6 in accordance with its use, typical ones used as techniques for enhancing safety of data are RAID 1, RAID 5, and RAID 6. RAID 1 is generally realized by use of two disks. This is the simplest method in which failure tolerance of the disks is enhanced by writing the same data to two disks, and called mirroring.
FIG. 1 is a distributed storage system to which RAID 1 is applied. In FIG. 1, to a main storage 100 connected via a network 102 are local storages 104-1 to 104-3 which function as distributed storages. In RAID 1, all the local storages 104-1 to 104-3 have data 106 that is same as the main storage 100, i.e., copy data 106-1 to 106-3 which is same as the data 106 of the main storage device 100; and when the data 106 of the main storage 100 is lost, data is transferred from any one of the local storages 104-1 to 104-3 so as to restore the lost data 106. RAID 5 is a method in which data is recorded in a manner that it is distributed to a plurality of disks, wherein, upon writing, a redundant code called parity obtained by addition of data is generated and written at the same time. Accordingly, even if any one of the disks fails, the original complete data can be restored from the data and parity information of the disks other than that.
FIG. 2 shows distributed storages to which RAID 5 is applied. The data of the main storage 100 is divided into data 108 and 110, and parity 112 is generated; and these are distributed to and stored in the local storages 104-1 to 104-3. In this case, for example, even if the data 110 is lost due to failure or the like of the local storage 104-2, the lost data 110 can be restored from the data 108 and the parity 112 of the local storage devices 104-1 and 104-3. RAID 6 is an extended version of RAID 5, wherein two pieces of parity are generated which is one in RAID 5. Accordingly, even if two disks fail at the same time, the original data can be restored in this method. Although there are several methods for obtaining the second parity, the Read Solomon code is generally employed.
FIG. 3 shows distributed storages to which RAID 6 is applied. The data of the main storage 100 is divided into data 108 and 110, and parity 112 and 114 is generated; and they are distributed to and stored in local storages 104-1 to 104-4. In this case, for example, even if data of two of the local storages 104-1 to 104-4 is lost due to failure or the like, the lost data can be restored from the data and/or parity of the two units of them which are normal. Moreover, as a conventional control method of a distributed storage system, when data is to be saved to a plurality of storages, it is made to be redundant in a doubled manner, thereby enabling restoration of data even when failure occurs in the storages
In addition, as a data storage method utilizing a wide-area distributed storage system, security of data is improved by distributing and storing data to and in a plurality of storages, and, at the same time, optimum setting of the storages is selected in consideration of physical distances between the storages, thereby improving line efficiency and safety of the data in a disaster.
However, when back up is performed by the mirroring method of RAID 1 with respect to such conventional plurality of local storages which are geographically distributed, the copy of the original data is generated in each local; therefore, there is a problem that, although failure tolerance is high, the utilization efficiency of the storages is extremely bad. Moreover, although the utilization efficiency of the storages is high in RAID 5 compared with RAID 1, a restorable case is merely when one local storage fails, and restoration is impossible when two or more units thereof fail at the same time. Furthermore, RAID 6 has problems that the utilization efficiency is lower than RAID 5 by an amount corresponding to one disk since two pieces of parity are generated, and the calculation amount is large since the Read Solomon code is used for obtaining the second parity. On the other hand, the method of Patent Document 1 is a method in which double redundancy is performed when data is to be saved to a plurality of storages, thereby enabling restoration of the data even if failure occurs in the storage and speeding up read-out; however, when two or more storages fail at the same time, the data cannot be recovered. The method of Patent Document 2 is a method in which security of data is improved by distributing and storing the data to and in a plurality of storages; however, it has a problem that the utilization efficiency of the storages is bad since the data amount stored in each storage is the same.